package com.lx.algorithm.BinarySort;

/**
 * Description:  二分查找
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-09-01 17:22:31
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-09-01     张李鑫                     1.0         1.0 Version
 */
public class BinarySearch {

    /**
     * <p>
     * 二分查找 是否存在某个数
     * </p>
     *
     * @param arr
     * @param num
     * @return boolean
     * @Author zlx
     * @date 2021/9/1
     */
    public static boolean BinarySearch(int[] arr, int num) {
        int L = 0;
        int R = arr.length - 1;
        int mid = 0;
        while (L < R) {
            //等同于相加/2 但是相加会有越界风险
            mid = L + ((R - L) >> 1);
            if (arr[mid] > num) {
                R = mid - 1;
            } else if (arr[mid] == num) {
                return true;
            } else {
                L = mid + 1;
            }
        }
        return arr[L] == num;
    }


    /**
     * <p>
     * 在一个有序数组中找<=某个数最右侧的位置
     * </p>
     *
     * @param arr
     * @param num
     * @return int
     * @Author zlx
     * @date 2021/9/1
     */
    public static int BinarySearchLeft(int[] arr, int num) {
        int L = 0;
        int R = arr.length - 1;
        int mid = 0;
        int index = -1;
        while (L <= R) {
            //等同于相加/2 但是相加会有越界风险
            mid = L + ((R - L) >> 1);
            if (arr[mid] > num) {
                index = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return index;
    }


    /**
     * <p>
     * 局部最小值的问题
     * </p>
     *
     * @param arr
     * @param
     * @return int
     * @Author zlx
     * @date 2021/9/1
     */
    public static int min(int[] arr) {
        if (arr[0]<arr[1]){
            return arr[0];
        }
        if (arr[arr.length-1]<arr[arr.length-2]){
            return arr[arr.length-1];
        }

        int left=1;
        int right=arr.length-2;
        int mid=0;
        while (left<right){
            mid = left + ((right - left) >> 1);
            if (arr[mid]>arr[mid-1]){
                right=mid-1;
            }else if (arr[mid]>arr[mid+1]){
                left=mid+1;
            }else {
                return mid;
            }
        }
        return left;
    }
}
